package com.janlei.tree;

/**
 * 红黑树结构
 */
public class RedBlackTree {

    private final int R = 0;    //red
    private final int B = 1;    //black

    private Node root;          //rootNode

    class Node {
        int data;
        int color = R;

        Node left;
        Node right;
        Node parent;

        public Node(int data) {
            this.data = data;
        }
    }

    /**
     * 插入
     *
     * @param root
     * @param data
     */
    public void insert(Node root, int data) {
        //找到插入位置
        if (root == null)
            return;

        //data>root.right 向右下滑
        if (root.data < data)
            if (root.right == null)
                root.right = new Node(data);
            else
                insert(root.right, data);
            //data<=root.left 向左下滑
        else if (root.left == null)
            root.left = new Node(data);
        else
            insert(root.left, data);
    }

    /**
     * 左旋
     */
    public void leftRotate(Node node) {
        if (node.parent == null) {
            Node E = root;
            Node S = E.right;

            E.right = S.left;
            S.left.parent = E;

            E.parent = S;
            S.parent = null;
        }
    }

    /**
     * 右旋
     */
    public void rightRotate() {
    }

}
